1. Field of the Invention
The invention relates to packet switches for data communications and telephony traffic and, more particularly, to the control of the flow of information routed through such switches.
2. History of the Prior Art
In modern telecommunication systems, information is grouped together in units of data referred to as "packets" or "cells", each containing a data field comprising an address to which the cell is to be delivered and another data field which defines the information to be transferred to that address. A cell may also contain a data field containing the address of the source from which the cell originated. Such data cells are conventionally routed through communication systems from a source to a destination by means of packet switches which route the cells through a data network in accordance with the address information contained within them. Such packet switches receive a flow of data cells over one or more incoming links, read the addresses on the cells, and then route them out of the switch on one or more outgoing links toward their intended destinations.
The continuous flow of data cells in packet switches used in implementation of the telecommunications standard known as asynchronous transfer mode (ATM), as specified by the International Telegraph and Telephone Consulting Committee (C.C.I.T.T.), is illustratively shown in FIG. 1. The destination of each cell 1 is determined by an identifier address, known as a label 2, which is transmitted with and forms a part of each cell. A payload 3 contains transported user data.
Packet switches are constructed and function so that several cells intended for a single destination may arrive at the switch simultaneously over a plurality of different links. For example, in FIG. 2 there is illustrated the circumstance in which two different cells arrive at a packet switch 10 at the same time via two separate incoming links 11 and 12 and both are destined for the single outgoing link 13. Since the transmission capacity of each link is limited, the outgoing link 13 is able to handle only one of the cells at any given moment in time. The other cell must be stored temporarily in a buffer until it can be sent out over the outgoing link 13 by the switch 10. If a plurality of data cells addressed to link 13 arrive on the incoming links 11 and 12 over a longer period of time with a data rate which exceeds the capacity of the outgoing link 13, the need for buffering the cells addressed to link 13 will become even greater. If the packet switch 10 has insufficient space to buffer these cells, a certain number of the cells will be lost during high traffic load periods. Thus, the ability of the packet switch 10 to handle situations in which the traffic toward one link is extremely high will depend upon the buffering capacity of the switch itself.
There are two conventional methods to achieve packet switch buffering. One method includes the use of input buffers to the switch and the other includes the use of output buffers. In the situations in which input buffers are employed, data cells are buffered on the incoming links. The data cells are then taken or "plucked" from within the buffers and switched to the correct outgoing links through the intermediary of a crosspoint matrix. For example, in the illustration shown in FIG. 3, a plurality of incoming links 14-16 are connected respectively to input buffers 17-19 the output of each of which leads to a switch matrix 21. Data cells are written into and read from each input buffer 17-19 on a first-in, first-out basis, at a rate which is not greater than the capacity of the incoming links 14-16. This enables the input buffers to be implemented in a relatively simple manner even in the case of packet switches of relatively high individual link capacity. As a result, in terms of space for buffering cells, very large capacity input buffers can be readily constructed, and the size of the input buffers can be adapted to the nature of the traffic on the particular link to which each individual input buffer is connected.
When the data cells are plucked from within the input buffers 17-19, it is possible that all of the cells which are first in the queue within each of the three buffers 17-19 have the same destination. In such cases, it is necessary to serve the buffers one after the other. While an input buffer is waiting to be served, all of the data cells in that buffer will wait, including those cells which lie further down in the queue and which are addressed to and destined for outgoing links which have no load on them at that particular moment. This, so-called, head-of-the-line (HOL) problem makes it impossible to fully utilize the capacity of a packet switch which is equipped with input buffers.
One way of avoiding the HOL-problem in a packet switch configuration is by equipping the switch with output buffers. A switch of this type has an output buffer at each outgoing link, and data cells from all incoming links can be written into the buffer of the output link defined by the address within each cell. For example, there is shown in FIG. 4 a plurality of output buffers 22-24 each of which is connected respectively to an output link 25-27 and is shown receiving data cells addressed to each one via incoming links 31-33.
A major problem with a configuration using output buffers, however, is that each output buffer must have the capacity and bandwidth to store information cells arriving near simultaneously from multiple input links. In the worst-case scenario, the output buffers must be able to store data arriving simultaneously from every input link on the switch. This makes the implementation of output buffers extremely difficult and expensive. In FIG. 4 it can be seen that it is possible that data cells which are destined for the same outgoing link, e.g., outgoing link 25, may arrive at output buffer 22 near simultaneously on all three of the incoming links 31-33. Therefore each output buffer must have sufficient bandwidth to write data from all incoming links into the output buffer at a speed which will avoid the loss of data cells. Since ATM switches operate at data rates of 150 megabits per second, it is extremely difficult and expensive to construct output buffers of sufficient bandwidth and memory capacity.
While certain solutions to these problems have been proposed, such as, for example, the use of intermediate output buffers or the common use of one output buffer which splits to several individual outputs, these solutions have not been adequate. The large bandwidth required of output buffers in multiple input packet switches, in order to avoid the loss of data at high transfer rates, makes it very difficult to construct output buffers of adequate capacity. These output buffering problems are particularly acute in the case of packet switches employed in systems which implement asynchronous transfer mode (ATM) data transfer and operate at data rates in excess of 150 megabits per second.
Packet switches in ATM systems may be implemented in a single device comprising input buffers, a switch fabric which performs the actual switching operation, and output buffers. Alternatively, an ATM switch may be implemented in two parts called a switch port and a switch core. The switch port, in turn, may have two sides, an input side and an output side. The input side of the switch port interfaces with an associated incoming communications network, terminates the incoming ATM link, and performs the input buffering functions. The switch port is connected to the switch core which then performs the switching operation. Data cells are then sent to the output side of the switch port to which they are addressed, where the output buffering functions are performed.
It would be a distinct advantage to employ a switching configuration which employs both input buffering to a packet switch as well as output buffering in an efficient and economical manner which solves the problem of simultaneously requiring large buffer capacity and bandwidth.